package org.labuladong.动态规划算法.一维DP;

/**
 * @author Fql18
 * @Auther: qingle
 * @Date: 2024/10/26-14:15
 * @Description:
 *
 * 给定⼀个整数数组 nums，找到⼀个具有最⼤和的连续⼦数组（⼦数组最少包含⼀个元素），返回其最⼤和。
 * 示例 1：
 * 输⼊：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续⼦数组 [4,-1,2,1] 的和最⼤，为 6。
 *
 * 代码解释：
 * maxSum 用来记录遍历过程中找到的最大子数组和。
 * currentSum 用来记录包含当前元素的子数组的和。
 * 我们从数组的第二个元素开始遍历，对于每个元素，我们决定是将其加入到已有的子数组中（currentSum + nums[i]），还是单独作为一个子数组（nums[i]）。
 * 在每次迭代中，我们更新 currentSum 为 nums[i] 和 currentSum + nums[i] 中的较大值，这相当于在每个步骤中做出贪心选择。
 * 然后，我们更新 maxSum 为 maxSum 和 currentSum 中的较大值。
 * 最终，maxSum 包含了整个数组的最大子数组和。
 * 这种方法的时间复杂度为 O(n)，其中 n 是数组 nums 的长度，因为我们只需要遍历一次数组。空间复杂度为 O(1)，因为我们只使用了有限的额外空间。
 *
 * 每次状态转移都是基于前一个状态的，这意味着我们总是在考虑包含当前元素的连续子数组。这里的“连续”是相对于数组元素的索引而言的，而不是数组元素的值。
 * @version: 1.0
 */
public class LC_53大子序和DP2 {

	public static int maxSubArray(int[] nums) {
		// 初始化最大和为数组的第一个元素，也可以初始化为Integer.MIN_VALUE
		int maxSum = nums[0];
		// 初始化当前和为数组的第一个元素
		int currentSum = nums[0];

		// 从数组的第二个元素开始遍历
		for (int i = 1; i < nums.length; i++) {
			// 更新当前和，当前和可以是它自身的值（如果之前的和为负数，加上会更小）
			// 或者是之前和加上当前值（如果之前的和为正数，可以增加当前和）
			currentSum = Math.max(nums[i], currentSum + nums[i]);
			// 更新最大和，如果当前和大于最大和，则更新最大和
			maxSum = Math.max(maxSum, currentSum);
		}

		// 返回遍历结束后的最大和
		return maxSum;
	}
	public static void main(String[] args)
	{
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		int max = maxSubArray(nums);
		System.out.println(max);
	}
}
